import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/6 9:16
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] edges = {{3,0},{3,1},{3,2},{3,4},{5,4}};
        solution.findMinHeightTrees(6, edges);
    }
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        int[] inDegree = new int[n];
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            inDegree[edge[0]]++;
            inDegree[edge[1]]++;
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 1) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            // 每一层都要new 一个新的结果集合，到最后一层时就是最终的最小高度树
            res = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                res.add(cur);
                List<Integer> neighbors = graph[cur];
                for (int ne: neighbors) {
                    inDegree[ne]--;
                    if (inDegree[ne] == 1) {
                        queue.add(ne);
                    }
                }
            }
        }
        return res;
    }
}
